import Random._

def genRandom(x:Int):List[Int]= {
    if(x<=0) Nil
    else Random.nextInt(1000) :: genRandom(x-1)
}
def msort(xs:List[Int]):List[Int]= {
    if(xs==Nil) Nil
    else if(xs.length==1) xs
    else {
        val n=xs.length/2
        val l1=msort(xs take n)
        val l2=msort(xs drop n)
        merge(l1,l2)
    }

}

def merge(xs:List[Int],ys:List[Int]):List[Int]= {
    if(xs.isEmpty) ys
    else if (ys.isEmpty) xs
    else {
        if(xs.head<ys.head) xs.head :: merge(xs.tail,ys)
        else ys.head::merge(ys.tail,xs)      

    }
        
}

val l1=List(2,3,4,5,6)
val l2=List(2,34,56,78)
//println(merge(l1,l2))

val l3=genRandom(10)
//println(l3)
//println(msort(l3))

def verify(xs:List[Int]):Boolean= {
    if(xs.length<=1) true
    else {
        if(xs.head>(xs.tail).head) {
            false
        }
        else verify(xs.tail)
    }
}
def verify2(xs:List[Int]):Boolean= {
    if(xs==Nil) true
    else {
    val a=xs zip xs.tail
    a forall((p) => p._1<=p._2)
    }
}
//println(verify2(List(2,4,5,6,7)))

// -- Testing Merge Sort using the in-built test suite
test("Merge Works") {
    val l1 = List(2, 3, 4, 5, 6)
    val l2 = List(2,34,56,78)
    val mergedl1l2 = List(2, 2, 3, 4, 5, 6, 34, 56, 78)
    merge(l1, l2) should equal(mergedl1l2)
    merge(Nil, Nil) should equal(Nil)
    merge(l1, Nil) should equal(l1)
    merge(Nil, l2) should equal(l2)
}
